class Node:
    def __init__(self):
        self.children=[None]*26 
        self.isend=False 

class Trie:
    def __init__(self):
        self.root=Node() 

    def insert(self,word):
        cur=self.root
        for ch in word:
            idx=ord(ch)-ord('a')
            if not cur.children[idx]:cur.children[idx]=Node()
            cur=cur.children[idx]
        cur.isend=True 

    def search_prefix(self,prefix):
        cur=self.root
        for ch in prefix:
            cur=cur.children[ord(ch)-ord('a')]
            if not cur: return None 
        return cur 
    
    def search(self,word):
        cur=self.search_prefix(word)
        if cur and cur.isend: return True 
        else: return False 

    def startwith(self,word):
        return self.search_prefix(word)!=None
    

def solve(lst1,lst2):
    trie=Trie()
    ans=[None]
    for i in range(1,len(lst1)):
        if lst1[i]=='insert':
            trie.insert(lst2[i][0])
            ans.append(None)
        elif lst1[i]=='search':
            ans.append(trie.search(lst2[i][0]))
        else:
            ans.append(trie.startwith(lst2[i][0]))
    return ans 

lst1=["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
lst2=[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
print(solve(lst1,lst2))



